/**
 * 145. 二叉树的后序遍历
 *
 * 【简单】
 *
 * 给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
 *
 * 示例 1：
 *
 *
 * 输入：root = [1,null,2,3]
 * 输出：[3,2,1]
 * 【https://assets.leetcode.com/uploads/2020/08/28/pre1.jpg】
 * 示例 2：
 * 输入：root = []
 * 输出：[]
 *
 * 示例 3：
 * 输入：root = [1]
 * 输出：[1]
 */

import { TreeNode } from '../utils/tree'

// 递归
var postorderTraversal = function postorderTraversal(
	root: TreeNode | null
): number[] {
	if ((root = null)) {
		return []
	}

	const res: number[] = []
	const dfs = (root) => {
		if (root == null) {
			return
		}
		if (root.left) {
			dfs(root.left)
		}
		if (root.right) {
			dfs(root.right)
		}

		res.push(root.val)
	}

	dfs(root)
	return res
}

// 迭代
var postorderTraversal = function postorderTraversal(
	root: TreeNode | null
): number[] {
	if (root == null) {
		return []
	}
	const res: number[] = []
	const stack: TreeNode[] = [root!]
	while (stack.length) {
		root = stack.pop()!
		res.unshift(root.val)
		if (root?.left) {
			stack.push(root.left)
		}
		if (root?.right) {
			stack.push(root.right)
		}
	}

	return res
}
